#!/usr/bin/env/python3
# -*- coding: utf-8 -*-

"""
@Time    : 2020/3/3 14:31
@Author  : Chen Liu
@FileName: class_2.py
@Software: PyCharm
"""


# 找入度为0的点,纠结的两个点：1.如何找入度为0的点？2.如何终止循环？
# 解法一超时，迭代的终止条件不对
# class Solution:
#     def findOrder(self, numCourses, prerequisites):
#         if not numCourses:
#             return []
#         if not prerequisites or not prerequisites[0]:
#             return [i for i in range(numCourses)]
#         courses = [i for i in range(numCourses)]
#         length = len(prerequisites)
#         d = {}
#         for i in range(numCourses):
#             d[i] = []
#             for j in range(length):
#                 key = prerequisites[j][0]
#                 # print("key: ", key)
#                 value = prerequisites[j][1]
#                 # print("value: ", value)
#                 if i == key:
#                     d[i].append(value)
#
#         print(d)
#
#         sorted_list = []
#         while courses:
#             length = len(courses)
#             for j in range(numCourses):
#                 if not d[j] and j in courses:  # 入度为0
#                     for key, value in d.items():
#                         print("j: ", j)
#                         if value and j in value:
#                             print(":value:", value)
#                             value.remove(j)
#                         print("courses ", courses)
#                     courses.remove(j)
#                     sorted_list.append(j)
#
#             if length == len(courses):
#                 break
#
#         if courses:
#             return []
#         else:
#             return sorted_list


# 解法二：预先构造一个循环成立的条件，然后利用长度的变化情况来衡量。
# class Solution:
#     def findOrder(self, numCourses, prerequisites):
#         d = {}
#         for a, b in prerequisites:
#             d[a] = d[a] + [b] if a in d else [b]
#
#         class_id = list(range(numCourses))
#         res = []
#         # 预先设置一个成立的条件
#         t = len(class_id) + 1
#         # 观察class_id的长度是否发生变化，终止循环
#         while len(class_id) < t:
#             t = len(class_id)
#             for id in class_id:
#                 if id not in d:
#                     # for key, value in d.items(): 这样后面删除d里面的键会报错
#                     for x in list(d.keys()):
#                         if id in d[x]:
#                             d[x].remove(id)
#                             if not d[x]:
#                                 d.pop(x)
#                     class_id.remove(id)
#                     res.append(id)
#         print(res)
#         print(class_id)
#         return res if class_id == [] else []

# 解法三：深度优先遍历--递归
class Solution:
    def findOrder(self, numCourses, prerequisites):
        graph = [[] for _ in range(numCourses)]
        for a, b in prerequisites:
            graph[a].append(b)

        visited = [0] * numCourses
        res = []

        def dfs(i):
            if visited[i] == 1:
                return True
            if visited[i] == -1:
                return False

            visited[i] = -1
            for pre in graph[i]:
                if not dfs(pre):
                    return False
            visited[i] = 1
            res.append(i)

            return True

        result = []
        for i in range(numCourses):
            if not dfs(i):
                return []
            else:
                result += res
                res = []
        return result


if __name__ == "__main__":
    s = Solution()
    num = 2
    p = [[1, 0]]
    res = s.findOrder(num, p)
    print("res:", res)
